package com.cty.twentySixthDay;

import java.util.LinkedList;
import java.util.Queue;

/*
给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
* */
public class Q_37 {

    // 力扣官方题解 方法一:深度优先算法
    /*
     * 思路:
     *   递归的去遍历左右子树
     *   每次去递归结果的最大值 + 1
     *   因为遍历到了这一层就要加一
     *   时间复杂度O(n) 空间复杂度O(height) 二叉树的高度 因为要用到栈(递归需要)
     * */
    public int maxDepth(TreeNode root) {
        // 判断当前的节点是否为空 为空返回0
        if (root == null) return 0;
        // 返回每一层加一 取左右子树遍历的最大值 作为当前节点的高度
        return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
    }

    // 力扣官方题解 方法二:广度优先算法
    /*
     * 思路:
     *   利用广度优先算法的思想
     *   将遍历的同一层的节点加入
     *   队列中 依次遍历队列
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        int ans = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // 记录当前队列的长度 (也就是记录当前一层节点的总数)
            int size = queue.size();
            while (size != 0) {
                // 将下一层的节点全部加入队列中
                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }
                size--;
            }
            //本层的全部出栈之后 加下一层的元素全部加进来 树的高度加一
            ans++;
        }
        return ans;
    }
}
